package java;

/**
 * 这个类时一个模拟indexOf功能
 * @author HuWLin
 * */
public class IndexOf {
    /*
     * KMP算法
     * 时间复杂度为O(m + n)
     * @param haystack
     *        被匹配字符串
     * @param needle
     *        匹配字符串
     * @return
     *        返回匹配字符串所在被匹配字符串位置
     * */
    public static int kmp(String haystack, String needle){
        int m = haystack.length(),n = needle.length();
        if(n == 0){
            return 0;
        }
        //用来存放，i < n,长度为i + 1的时候字符串前半部分和后半部分相同长度，
        //例如"abcab"的same的值为[0,0,0,1,2],"abcdea",[0,0,0,0,0,1]
        int[] same = new int[n];
        //以下循环是进行计算,sameCount存放，从1开始是因为第一位只有一个数不存在前后部分，只能为0
        for(int i = 1,sameCount = 0;i < n;i ++){
            //当遇到不相同时，并且最长的相同大于0的情况，寻找长度为sameCount 前后重复的位数,以此进行一个向前找，一直找到0为止
            //用递减的方式寻找会浪费很多时间，这也是kmp的核心算法
            //此处不易理解，例如"aaabbaab",[0,1,2,0,0,1,2,0]
            while(sameCount > 0 && needle.charAt(i) != needle.charAt(sameCount)){
                sameCount = same[sameCount - 1];
            }
            //如果相同sameCount就自增
            if(needle.charAt(i) == needle.charAt(sameCount)){
                sameCount ++;
            }
            //把当前最大的赋值给same[i]
            same[i] = sameCount;
        }
        //这边与上面类似，只是少了赋值环节
        for(int i = 0,sameCount = 0;i < m;i ++){
            while(sameCount > 0 && haystack.charAt(i) != needle.charAt(sameCount)){
                sameCount = same[sameCount - 1];
            }
            if(haystack.charAt(i) == needle.charAt(sameCount)){
                sameCount ++;
            }
            if(sameCount == n){
                return i - n + 1;
            }
        }
        return -1;

    }
}
